import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-09-14
 * Time: 22:17
 */
public class Solution {
    /**
     *  方法一: 排序 + 二分查找
     *  O(N^2 * logN)
     */
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        int ans = 0;
        int len = nums.length;
        for (int i = 0; i < len - 2; i++) {
            for (int j = i+1; j < len-1; j++) {
                int index = binarySearch(nums[i]+nums[j], j+1, nums);
                ans += index - j - 1;
            }
        }
        return ans;
    }

    private int binarySearch(int val, int index, int[] nums) {
        int left = index;
        int len = nums.length;
        // 注意 最终结果是可以等于 len 的
        int right = len;
        while (left < right) {
            int mid = ((right-left)>>1) + left;
            if (nums[mid] < val) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }


    /**
     *  方法二: 排序 + 双指针
     *  固定 i, j 增大的话, k 一定也增大
     *  所以 在 j 的循环中 k 只使用一个即可, 因为 k 是一直增大的
     *  时间复杂度为 O(N^2)
     */
    public int triangleNumber2(int[] nums) {
        Arrays.sort(nums);
        int ans = 0;
        int len = nums.length;
        int i = 0;
        // 跳过值为 0 的情况
        while (i < len && nums[i] == 0) i++;
        for (; i < len - 2; i++) {
            int k = i + 2;
            for (int j = i+1; j < len-1; j++) {
                while (k < len && nums[k] < (nums[i]+nums[j])) k++;
                ans += k-j-1;
            }
        }
        return ans;
    }
}